package com.cat.dataStructure02;

import java.util.Arrays;

/**
*   @description https://leetcode.cn/problems/maximum-sum-obtained-of-any-permutation/description/
*   @author 曲大人的喵
*   @create 2025/10/23 15:48
*   @since JDK17
*/

class Solution51 {
    static int N = (int) (1e9  + 7);
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        int n = nums.length;
        long ans = 0;
        int[] diff = new int[n + 1];
        for (var r : requests) {
            int s = r[0], e = r[1];
            diff[s]++;
            diff[e + 1]--;
        }
        for (int i = 1; i <= n; i++) {
            diff[i] += diff[i - 1];
        }
        Arrays.sort(diff);
        Arrays.sort(nums);
        for (int i = n, j = n - 1; diff[i] > 0 && j >= 0; i--, j--) {
            ans = (ans + (long) nums[j] * diff[i]) % N;
        }

        return (int) ans;
    }
}
